/**
 * \* Created with IntelliJ IDEA.
 * \* User: Administrator
 * \* Date: 2021/12/6
 * \* Time: 17:13
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */

//ListNode代表一个节点
class ListNode{
    public int val;
    public ListNode next;

    public ListNode(int val){
        this.val=val;
    }

}

public class MyLinkedList {
    public ListNode head;//链表的头引用

    public void creatList(){
        ListNode listNode1=new ListNode(12);
        ListNode listNode2=new ListNode(13);
        ListNode listNode3=new ListNode(14);
        ListNode listNode4=new ListNode(15);
        ListNode listNode5=new ListNode(16);

        listNode1.next=listNode2;
        listNode2.next=listNode3;
        listNode3.next=listNode4;
        listNode4.next=listNode5;
        this.head=listNode1;
    }

    public void display(){
        ListNode cur=this.head;
        while (cur!=null){
            System.out.print (cur.val+" ");
            cur=cur.next;
        }
        System.out.println();
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        ListNode cur=this.head;
        while (cur!=null){
            if (cur.val==key)return true;
            cur=cur.next;
        }
        return false;
    }

    //得到单链表的长度
    public int size(){
        int count=0;
        ListNode cur=this.head;
        while (cur!=null){
            count++;
            cur=cur.next;
        }
        System.out.println(count);
        return -1;
    }
    //头插法
         void addFirst(int data) {
            ListNode node=new ListNode(data);
            if(this.head==null){
                this.head=node;
            }else {
                node.next=this.head;
                this.head=node;
            }
         }
   //尾插法
           public void addLast(int data){
                ListNode node=new ListNode(data);
               if(this.head==null){
                   this.head=node;
               }else {
                   ListNode cur = this.head;
                   while (cur.next!=null){
                       cur=cur.next;
                   }
                   cur.next=node;
               }

             }
             public ListNode findIndex(int index){
                ListNode cur=this.head;
                while (index-1!=0){
                    cur=cur.next;
                    index--;
                }
                return cur;
             }
   //任意位置插入,第一个数据节点为0号下标
           public void addIndex(int index,int data){
               if (index<0 || index > size()){
                   System.out.println("位置不合法");
               }
               if(index==0){
                   addFirst(data);
                   return;
               }
               if (index==size()){
                   addLast(data);
                   return;
               }
                ListNode cur= findIndex(index);
               ListNode node=new ListNode(data);
               node.next=cur.next;
               cur.next=node;
             }

             public ListNode searchPrev(int key){
                ListNode cur=this.head;
                while (cur.next!=null){
                    if(cur.next.val==key){
                        return cur;
                    }
                    cur=cur.next;
                }
                return null;
             }
   //删除第一次出现关键字为key的节点
           public void remove(int key){

                if(this.head==null){
                    System.out.println("单链表为空，不能删除");
                }
                if (this.head.val==key){
                    this.head=this.head.next;
                    return;
                }
              ListNode cur=searchPrev(key);
                if(cur==null){
                    System.out.println("没有删除的节点");
                    return;
                }
                ListNode del=cur.next;
                cur.next=del.next;
             }
//删除所有值为key的节点
         public ListNode removeAllKey(int key){
            if(this.head==null)return null;
            ListNode prev=this.head;
            ListNode cur=this.head.next;

            while (cur!=null){
                if(cur.val==key){
                    prev.next=cur.next;
                    cur=cur.next;
                }else {
                    prev=cur;
                    cur=cur.next;
                }
            }
            if(this.head.val==key){
                this.head=this.head.next;
            }
            return this.head;
             }

         public void clear(){
            while (this.head!=null){
                ListNode cutNext=head.next;
                this.head.next=null;
                this.head=cutNext;
            }
             }

}
